Binary Trees
basic concepts of binary trees
07 Oct 2017
View Comments
#binary
#tree
#traversal
#programming
“Binary tree” is the tree in which every node has at most 2 children, which are referred to as the left child and the right child. Trees can certainly have multiple leaves (n-ary, b-tree), trie structure, heap structure and much more. Binary Tree is one of the simple and popular tree structure out of many kinds of trees. It really is basically a 2-ary tree. The tree is often interchangeable with the undirected graph. In a binary tree, it is a graph with at most 2 edges stemming out of a to create at most 2 vertices at t. The topmost node in the tree is called the root. This is the vertice that starts the whole tree. Therefore typically, we refer to a binary tree as a directed graph since it begins from top to bottom in most of the case.
Types of Binary Tree
Full (Strict) Binary Tree
A binary tree T with n levels is “full” if the tree nodes have 0 or 2 children. Following are examples of full binary tree
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 20
/ \
40 50
/ \
30 50Complete Tree
A binary tree T with n levels is “complete” if all levels except possibly the last are completely full
18
/ \
15 30
/ \
40 50Full And Complete Tree
In a full binary tree,
- # of min nodes are \(n = h + 1 (root)\)
- # of max nodes are \(n = 2^{(h+1)} - 1\)
In a perfect binary tree (full and complete binary tree),
- # of min nodes are \(n = 2^{h}\)
- # of max nodes are \(n = 2^{(h+1)} - 1\)
Balanced Binary Tree
Before we define what balanced binary tree is, we should examine what height/depth of a tree is. The height of a node is the number of edges from the node to the deepest leaf. Now that we have the height in mind, what is a balanced tree? A rooted binary tree of height “h” is balanced if all leaves are perfect at levels h “or” h − 1. It is important to say that all complete trees are balanced trees, all balanced trees are not necessarily complete trees. See the example below:
x
x x
x x x
x Above is a balanced binary tree but not a complete binary tree.
Here is an example code (in Java) which checks whether given tree is balanced:
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int diff = getHeight(root.left) - getHeight(root.right);
if (Math.abs(diff) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}Note there is a function for calculating the height because it needs to know that to understand the tree is balanced. Basically the function recurses all the way down to the tree by validating the height difference (cannot be greater than 1)until the base case is hit (root == null).
Binary Search Tree (BST)
We saw what it means to be a tree to be balanced. Here is another form of a binary tree that allows for a faster search. It produces O(log n) when a tree is balanced. When a tree with n nodes is kept balanced, its height is always O(log n). This is why we have self-balancing (height-balanced) binary search trees such as AVL (1962), 2-3 Tree (1970) or Red-Black Tree (1972). These trees would make additional effort in insertion/removal of the nodes to keep the tree balanced by rotating trees around in an efficient way to keep the complexity at O(log n). Without balancing the trees, the tree could be skewed to one side. In extreme cases, it would basically be a O(n) searching.
Check checkBST function to see how it validates BST:
public Integer last_printed = null;
public boolean checkBST(TreeNode n) {
if (n == null) {
return true;
}
// Check / recurse left
if (!checkBST(n.left)) {
return false;
}
// Check current
if (last_printed != null && n.val <= last_printed) {
return false;
}
last_printed = n.val;
// Check / recurse right
if (!checkBST(n.right)) {
return false;
}
return true;
}Above code would recurse left tree first and check whether all nodes are in BST mode. Then check the right by doing the same check. When every nodes are validated, the function returns “PASS”.
Here is a bit more simpler way of check using recursion:
private boolean isValidBST(Node node, int min, int max) {
if(node == null)
return true;
return node.value > min
&& node.value < max
&& isValidBST(node.left, min, node.value)
&& isValidBST(node.right, node.value, max);
}Above code recurses left and right subtrees and check if the value is set properly to BST rule. Returns false if the tree violates the BST rule.
Tree Traversal
The idea of traversal on the tree really stemmed from graph traversal and applied to the tree which refers to the similar process of visiting each node. Since the traversal requires visiting all the nodes, the time complexity of this operation is usually O(n) either a tree or a graph. The difference between the traversal on graph vs tree would be an indication of whether the node is visited or not in a vertices because unlike the binary trees (top-down approach), graphs could have multiple branches/edges and can quickly recurse on the same traversal which could end up with infinite recursion unless we mark it properly as a “visited” node.
Depth-First Search (DFS)
Trees can be traversed using a Depth First Search algorithm. There are 3 different methods for traversing the tree and they all start from the root node.
Pre-order
Purpose of this traversal is to visit the root node before proceeding to each child nodes. Used for copying/cloning the tree.
Performed in this order recursively:
- Check if the current node is empty / null.
- Display the data part of the root (or current node).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
Here is an example code:
private Node preOrderCopy(Node n) {
if (n == null) {
// base case
return null;
}
Node copy = new Node(n.key, n.name);
copy.leftChild = preOrderCopy(n.leftChild);
copy.rightChild = preOrderCopy(n.rightChild);
return copy;
}In-order
This traversal is very useful in search trees, as it will retrieve and flatten the nodes in sorted order.
Performed in this order recursively:
- Check if the current node is empty/null.
- Traverse the left subtree by recursively calling the in-order function.
- Display the data part of the root (or current node).
- Traverse the right subtree by recursively calling the in-order function.
Here is an example code:
public List<Integer> findInorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
return findInorder(root, result);
}
private List<Integer> findInorder(TreeNode root, List<Integer> result) {
if (root == null) return result;
findInorder(root.getLeft(), result);
result.add(root.getVal());
findInorder(root.getRight(), result);
return result;
}Post-order
If you know you need to explore all the leaves first starting from the left side, use this traversal. This traversal is useful in an expression tree that is to do with calculating stuff.
Performed in this order recursively:
- Check if the current node is empty/null.
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).
Here is an example code:
void deleteTree(Node node)
{
if (node == null)
return;
/* first delete both subtrees */
deleteTree(node.left);
deleteTree(node.right);
/* then delete the node */
System.out.println("The deleted node is " + node.data);
node = null;
}Breadth-First Search (BFS)
Trees can also be traversed in level-by-level, where we visit every node on a level before going to a lower level. This search is referred to as breadth-first search (BFS), which interchangeably is called as level order tree traversal, as the search tree is broadened as much as possible on each depth before going to the next depth. Queue (FIFO collection) is used in the algorithm. The algorithm is often used to find the shortest path from one node to another. You can use an algorithm like Dijkstra’s algorithm to let you find a single-source shortest path from one node to another. BFS is used in many other cases depending on how the tree is structured.
public List<Integer> findBFS(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> tracker = new LinkedList<>();
tracker.add(root);
while(!tracker.isEmpty()) {
TreeNode node = tracker.remove();
result.add(node.getVal());
if (node.left != null) {
tracker.add(node.left);
}
if (node.right != null) {
tracker.add(node.right);
}
}
return result;
}Recursiveness
It is fairly common for the tree operations to run in recursion. Recursion is generally appropriate and useful when we have a structure that has a similar repeated structural form. A tree is really a recursive data type because a tree is made of another tree (subtrees) like a diagram below (recursively):
We are going to take a look at more operation side of trees in next blog post where you will be able to see how recursions are being used to conquer the problem.
